#ifndef FLFILL_H_
#define FLFILL_H_

#include <algorithm>
#include <vector>


namespace lxj
{
// 岛屿数量
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
// 此外，你可以假设该网格的四条边均被水包围
// 测试链接 : https://leetcode.cn/problems/number-of-islands/
class NumIslands {
    inline void dfs(std::vector<std::vector<char>>& grid, int n, int m, int i, int j)
    {
        if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != '1') return;
        grid[i][j] = 0;
        dfs(grid, n, m, i - 1, j);
        dfs(grid, n, m, i + 1, j);
        dfs(grid, n, m, i, j - 1);
        dfs(grid, n, m, i, j + 1);
    }

public:
    inline int numIslands(std::vector<std::vector<char>>& grid)
    {
        int n       = grid.size();
        int m       = grid[0].size();
        int islands = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    dfs(grid, n, m, i, j);
                }
            }
        }
        return islands;
    }
};

// 被围绕的区域
// 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域
// 并将这些区域里所有的 'O' 用 'X' 填充。
// 测试链接 : https://leetcode.cn/problems/surrounded-regions/
class SurroundedRegions {
    inline void dfs(std::vector<std::vector<char>>& board, int n, int m, int i, int j)
    {
        if (i < 0 || i == n || j < 0 || i == m || board[i][j] == 'X') return;
        board[i][j] = 'F';
        dfs(board, n, m, i - 1, j);
        dfs(board, n, m, i + 1, j);
        dfs(board, n, m, i, j - 1);
        dfs(board, n, m, i, j + 1);
    }

public:
    inline void solve(std::vector<std::vector<char>>& board)
    {
        int n = board.size();
        int m = board[0].size();

        for (int j = 0; j < m; j++) {
            if (board[0][j] == 'O') dfs(board, n, m, 0, j);
            if (board[n - 1][j] == 'O') dfs(board, n, m, n - 1, j);
        }
        for (int i = 1; i < n - 1; i++) {
            if (board[i][0] == 'O') dfs(board, n, m, i, 0);
            if (board[i][m - 1] == 'O') dfs(board, n, m, i, m - 1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'F') board[i][j] = 'O';
            }
        }
    }
};

// 最大人工岛
// 给你一个大小为 n * n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
// 返回执行此操作后，grid 中最大的岛屿面积是多少？
// 岛屿 由一组上、下、左、右四个方向相连的 1 形成
// 测试链接 : https://leetcode.cn/problems/making-a-large-island/
class MakingLargeIsland {
    inline void dfs(std::vector<std::vector<int>>& grid, int n, int m, int i, int j, int id)
    {
        if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != 1) return;
        grid[i][j] = id;
        dfs(grid, n, m, i - 1, j, id);
        dfs(grid, n, m, i + 1, j, id);
        dfs(grid, n, m, i, j - 1, id);
        dfs(grid, n, m, i, j + 1, id);
    }

public:
    inline int largestIsland(std::vector<std::vector<int>>& grid)
    {
        int n  = grid.size();
        int m  = grid[0].size();
        int id = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) dfs(grid, n, m, i, j, id++);
            }
        }

        std::vector<int> size(id);
        int              ans = 0;
        for (auto& i : grid) {
            for (auto value : i) {
                if (value > 1) ans = std::max(ans, ++size[value]);
            }
        }

        bool* visited = new bool[id];
        std::fill(visited, visited + id, false);
        int up, down, left, right, merge;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    up          = i > 0 ? grid[i - 1][j] : 0;
                    down        = i + 1 < n ? grid[i + 1][j] : 0;
                    left        = j > 0 ? grid[i][j - 1] : 0;
                    right       = j + 1 < m ? grid[i][j + 1] : 0;
                    visited[up] = true;
                    merge       = 1 + size[up];
                    if (!visited[down]) {
                        merge += size[down];
                        visited[down] = true;
                    }
                    if (!visited[left]) {
                        merge += size[left];
                        visited[left] = true;
                    }
                    if (!visited[right]) {
                        merge += size[right];
                        visited[right] = true;
                    }
                    ans            = std::max(ans, merge);
                    visited[up]    = false;
                    visited[down]  = false;
                    visited[left]  = false;
                    visited[right] = false;
                }
            }
        }
        delete[] visited;
        return ans;
    }
};

// 打砖块
// 有一个 m * n 的二元网格 grid ，其中 1 表示砖块，0 表示空白
// 砖块 稳定（不会掉落）的前提是：
// 一块砖直接连接到网格的顶部，或者
// 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
// 给你一个数组 hits ，这是需要依次消除砖块的位置
// 每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失
// 然后其他的砖块可能因为这一消除操作而 掉落
// 一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）
// 返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
// 注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
// 测试链接 : https://leetcode.cn/problems/bricks-falling-when-hit/
class BricksFallingWhenHit {
    inline static int              n, m;
    std::vector<std::vector<int>>* m_grid;

    inline int dfs(int i, int j)
    {
        if (i < 0 || i == n || j < 0 || j == m || (*m_grid)[i][j] != 1) return 0;
        (*m_grid)[i][j] = 2;
        return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1);
    }

    inline bool worth(int row, int col)
    {
        return (*m_grid)[row][col] == 1 && (row == 0 || (row > 0 && (*m_grid)[row - 1][col] == 2) ||
                                            (row < n - 1 && (*m_grid)[row + 1][col] == 2) ||
                                            (col > 0 && (*m_grid)[row][col - 1] == 2) ||
                                            (col < m - 1 && (*m_grid)[row][col + 1] == 2));
    }

public:
    inline std::vector<int> hitBricks(std::vector<std::vector<int>>& grid,
                                      std::vector<std::vector<int>>& hits)
    {
        n      = grid.size();
        m      = grid[0].size();
        m_grid = &grid;
        std::vector<int> ans(hits.size());
        if (n == 1) return ans;

        for (auto& h : hits) {
            grid[h[0]][h[1]]--;
        }
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 1) dfs(0, j);
        }

        for (int i = hits.size() - 1, row, col; i >= 0; i--) {
            row = hits[i][0];
            col = hits[i][1];
            grid[row][col]++;
            if (worth(row, col)) {
                ans[i] = dfs(row, col) - 1;
            }
        }
        return ans;
    }
};
}   // namespace lxj

#endif